1. Field of the Invention
This invention relates to a method of automatically detecting errors in computer programs, and more particularly to detecting errors in computer program caused by erroneous memory allocations and deallocations, flawed logic structure, and/or hardware malfunctions.
2. Description of Related Art
Computer programs, or "software", have become an increasingly important component of modern technology. General purpose computers, when specifically programmed, become special purpose machines for accomplishing a wide variety of functions, from word processing to real-time guidance control in aircraft and missiles.
Errors (or "bugs") in computer programs cause programs to malfunction in a variety of ways, with a wide range of unintended results, from annoying to disastrous. As computer programs have become more complex, "debugging" computer programs to eliminate such errors has become increasingly difficult, and has required an increasingly large percentage of program developer resources. Indeed, a sub-industry has developed in the field of computer programs specially designed to ease the burden of detecting, locating, and remedying program errors. Examples of such commercial products are Microsoft Corporation's "CODEVIEW" debugging program and Borland International Inc.'s "TURBO DEBUGGER" program.
While such debugging programs have made error detection and correction somewhat easier for computer programmers, one disadvantage of such programs is that they do not monitor a program in an operational setting after the program has been released for commercial use. That is, such debugging tools are generally limited to use only during program development.
A common source of program errors in complex software relates to dynamic allocation and deallocation of computer memory. The memory of a computer represents a finite resource, which must be carefully conserved. Memory space is divided into program code space, the "stack", and the "heap". The stack is a fixed-size memory block used for variables and defined by a compiler during compilation of a program. The "heap" is computer memory space outside of the program code space and the stack. The heap must be dynamically allocated and deallocated.
Large, complex programs, if loaded all at once, or by working with large data files, would normally exceed the memory resources of a typical computer. However, since not all program functions are generally needed at one time, and since large data files can usually be processed in segments, most large, complex programs dynamically allocate available memory resources depending upon the nature and requirements of each function. For example, a word processing program that has a spell checking capability does not normally need to maintain the spell checking program code in memory at all times. When the spell checking function is invoked by a user, memory currently in use by a portion of the program that is not needed during the spell checking routines may be deallocated, and that memory reallocated to the spell checking code and data. The same concept applies when working with complex data structures and large data files.
Dynamic allocation and deallocation of the heap permits a programmer to manage the memory needs of a large program. A number of computer program languages are particularly well suited to such dynamic memory allocation and deallocation. One example is the C language, widely used in a large number of programs. The principal command used in the C language to allocate a portion of memory is MALLOC (for "Memory ALLOCation"), and the principal command to deallocate memory is "FREE". Variations of these commands are known in the art, and are used with different programming "memory models".
Most languages that support dynamic memory allocation use "pointers" extensively (and sometimes exclusively) to track and access allocated blocks of memory. A pointer is a location in memory, generally given a name for ease of reference, which contains an address that "points" to an allocated memory block. Thus, a pointer is an indirect method of addressing a memory block.
A problem that frequently arises in programs that use dynamic memory allocation is misallocation of a memory block, or misuse of a pointer. For example, if a block of memory is allocated in a fashion that overlaps memory locations that are already in use, an error is likely to occur during operation. As another example, if the value of a pointer is inadvertently changed, and thereafter that pointer is used to access what is believed to be a correctly designated memory block, some other portion of memory will instead be accessed, generally causing a serious error. Such errors are also symptomatic of flaws in the logical structure of a computer program, since often the decision to make a dynamic memory allocation or deallocation is dependent on the logical structure of the program.
Because of the complexities of many programs, such errors are often undetected until a particular sequence of program code is executed, or a particular data event occurs, or a particular sequence of memory allocation, deallocation, and/or reference occurs. Further, due to the indirect referencing capabilities of pointer-intensive programs, it is possible for an error in one part of a program to cause error symptoms to appear in another, non-erroneous part of the program, thus making debugging very difficult. Moreover, the problem is compounded by the fact that certain types of hardware malfunctions--particularly intermittent errors--can cause a program to appear to have errors in logical structure.
Generally, it is almost impossible to simulate all possible program code combinations in developing computer software, and thus it is virtually impossible to detect all error conditions. Therefore, it is well known in the industry that most computer programs commercially available are sold with bugs in them, the occurrence of which may not be known for weeks, months, or even years after the programs are released.
Therefore, it is desirable to have a means for automatically detecting memory allocation and deallocation errors, and errors in the logical structure of a computer program. Moreover, it is desirable to have such a means which can be incorporated into software such that the error detecting function would continue to detect, or "trap", errors in an operational environment, rather than only in a development environment. It is also desirable to find errors caused or evidenced by bad memory allocations and deallocations or hardware malfunctions before the errors occur.
The present invention meets these goals.